/*
*
给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。

返回 优质数对 的总数。

示例 1：

输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1

输出：5

解释：

5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。

示例 2：

输入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3

输出：2

解释：

2个优质数对分别是 (3, 0) 和 (3, 1)。

提示：

1 <= n, m <= 105
1 <= nums1[i], nums2[j] <= 106
1 <= k <= 103

  - @author ala
  - @date 2024-10-10 10:19
*/
package main

import (
	"fmt"
)

func main() {
	//nums1 := []int{1, 3, 4}
	//nums2 := []int{1, 3, 4}
	//k := 1

	//nums1 := []int{1, 2, 4, 12}
	//nums2 := []int{2, 4}
	//k := 3

	nums1 := []int{1, 2, 4, 12}
	nums2 := []int{2, 4}
	k := 3

	fmt.Println(numberOfPairs(nums1, nums2, k))
}

func numberOfPairs(nums1 []int, nums2 []int, k int) int64 {
	//return V1(nums1, nums2, k)
	return V2(nums1, nums2, k)
}

/**
 *	枚举因子
 *	1）n1 能整除 n2 * k，说明 n1 能整除 k，并且 n1 / k 能整除 n2
 *	2）分解出 n1 / k 的所有因子，个数保存进hash表
 *	3）遍历 n2，累加n2作为因子的每个个数
 */
//func V1(nums1, nums2 []int, k int) int64 {
//	cnts := map[int]int64{}
//	for _, n := range nums1 {
//		if n%k != 0 {
//			continue
//		}
//		n /= k
//
//		for i := 1; i <= int(math.Sqrt(float64(n))); i++ {
//			if n%i == 0 {
//				cnts[i]++
//				i2 := n / i
//				if i2 != i {
//					cnts[i2]++
//				}
//			}
//		}
//	}
//
//	res := int64(0)
//	for _, n := range nums2 {
//		res += cnts[n]
//	}
//	return res
//}

/**
 *	枚举倍数
 *	1）nums1，nums2 的每个数统计个数
 *	2）如果 n1 能整除 n2 * k，累加 n1 和 n2 的个数和
 *		并且 2n1,3n1,4n1...也能整除 n2 * k
 */
func V2(nums1, nums2 []int, k int) int64 {
	cnts1, cnts2, mx1, mx2 := make([]int, 1e6+1), make([]int, 1e6+1), 0, 0
	for _, n := range nums1 {
		mx1 = max(mx1, n)
		cnts1[n]++
	}
	for _, n := range nums2 {
		mx2 = max(mx2, n)
		cnts2[n]++
	}

	res := int64(0)
	for _, n := range nums2 {
		if cnts2[n] > 0 {
			for d, i := n*k, n*k; i <= mx1; i += d {
				res += int64(cnts2[n]) * int64(cnts1[i])
			}
			cnts2[n] = 0
		}
	}
	return res
}
